#include <iostream>
#include <vector>
#include <list>
#include <forward_list>
#include <deque>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

class A {
private:
    int val;
public:
    A() : val(0) { cout << __PRETTY_FUNCTION__ << endl; }

    A(int v) : val(v) { cout << __PRETTY_FUNCTION__ << endl; }

    A(const A &other) : val(other.val) { cout << __PRETTY_FUNCTION__ << endl; }

    A &operator=(const A &a) {
        val = a.val;
        cout << __PRETTY_FUNCTION__ << endl;
        return *this;
    }

    bool operator==(const A &a) const { return val == a.val; }

    ~A() { cout << __PRETTY_FUNCTION__ << endl; }

    friend ostream &operator<<(ostream &, const A &);
};

ostream &operator<<(ostream &os, const A &a) {
    return os << a.val;
}

bool is_power_of_two(unsigned x) {
    return (x & (x - 1)) == 0;
}

void test_vector() {
    printf("-------------------------- %s -------------------------\n", __func__);
    /* vector在容量不足时，需要重新分配内存，拷贝或移动元素，释放原空间 */
    vector<A> vec_A;
    for (int i = 0; i < 17; ++i) {
        printf("插入第%d个元素\n", i + 1);
        if (is_power_of_two(i) and i > 0) {
            cout << "发生拷贝" << endl;
        }
        vec_A.emplace_back();
        cout << endl;
    }

    cout << "clear" << endl;
    vec_A.clear();
    cout << endl;

    /* 在预先知道元素数量的情况下，可以使用reserve()函数，预先申请内存，避免重复的分配、拷贝和释放 */
    cout << "reserve" << endl;
    vec_A.reserve(17);
    for (int i = 0; i < 17; ++i) {
        printf("插入第%d个元素\n", i + 1);
        vec_A.emplace_back();
        cout << endl;
    }
}

void test_iterator() {
    printf("-------------------------- %s -------------------------\n", __func__);
    vector<int> nums;
    for (int i = 0; i < 10; ++i) {
        nums.push_back(i);
    }

    for (auto it = nums.begin(); it != nums.end(); ++it) {
        ++(*it);
        cout << *it;
    }
    cout << endl;

    // cbegin, cend是const的迭代器
    for (auto it = nums.cbegin(); it != nums.cend(); ++it) {
        cout << *it;
        // ++(*it);
    }
    cout << endl;

    // 反向迭代器
    for (auto it = nums.rbegin(); it != nums.rend(); ++it) {
        cout << *it;
    }
    cout << endl;

    // C++11 range-based for
    for (auto x : nums) {
        cout << x;
    }
    cout << endl;
}

template<class T>
ostream &operator<<(ostream &os, const list<T> &lst) {
    for (auto &t: lst) {
        os << t << " ";
    }
    return os;
}

void test_list() {
    printf("-------------------------- %s -------------------------\n", __func__);
    list<int> list_A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    list<int> list_B = {1, 1, 1, 1, 1};

    // 将list_B的所有元素插入到list_A的5之前
    auto it = find(list_A.begin(), list_A.end(), 5);
    list_A.splice(it, list_B);
    cout << list_A << endl;
    cout << list_B << endl;

    // list必须使用自己的sort函数，不支持algorithm的sort，因为它需要随机访问
    list_A.sort();
    cout << list_A << endl;

    // 删除连续的相同元素
    list<int> list_C = {0, 0, 1, 1, 2, 2, 1, 1, 4, 4};
    list_C.unique();
    cout << list_C << endl; // 0 1 2 1 4

    // 归并两个排序后的list
    list<int> list_D = {0, 2, 4};
    list<int> list_E = {1, 3, 5};
    list_D.merge(list_E);
    cout << list_D << endl; // 0 1 2 3 4 5
    cout << list_E << endl; // 空

    // remove, remove_if
    list<int> list_F = {0, 1, 2, 3, 4, 0, 1, 2, 3, 4};
    list_F.remove(1); // 删除两个 1
    cout << list_F << endl; // 0 2 3 4 0 2 3 4
    list_F.remove_if([](int i) { return i % 2 == 0; }); // 删除偶数
    cout << list_F << endl;

    // 删除begin与end之间的元素
    list<int> list_G = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    auto begin = list_G.begin();
    auto end = list_G.begin();
    std::advance(begin, 1); // C++ 17
    std::advance(end, 3);
    list_G.erase(begin, end);
    cout << list_G << endl; // 0 3 4 5 6 7 8 9

    // 一边迭代一边删除和插入
    list<int> list_H = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    for (it = list_H.begin(); it != list_H.end();) {
        if (*it % 2 == 0) {
            it = list_H.erase(it); // erase返回的是删除元素的后一个元素
        } else {
            list_H.insert(it++, (*it) * 2); // insert会在当前节点之前插入元素
        }
    }
    cout << list_H << endl; // 2 1 6 3 10 5 14 7 18 9
}

template<class T>
ostream &operator<<(ostream &os, const deque<T> &lst) {
    for (auto &t: lst)
        os << t << " ";
    return os;
}

void test_deque() {
    printf("-------------------------- %s -------------------------\n", __func__);
    // deque内部并不是完全线性存储的，而是通过一个map指针数组与缓冲区配合，造成了deque是线性存储的假象
    deque<A> deq1 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    cout << deq1 << endl << endl;
    auto it = deq1.begin();
    std::advance(it, 2);
    // 插入到第三个元素之前，STL判断插入位置左右两段的长度，自动选择短的那一部分进行拷贝
    deq1.insert(it, -1);
    cout << deq1 << endl << endl;

    deq1.emplace_back(-1);
    cout << deq1 << endl << endl;

    deq1.emplace_front(-1);
    cout << deq1 << endl << endl;

    deq1.resize(10);
    cout << deq1 << endl << endl;
}

void test_stack() {
    printf("-------------------------- %s -------------------------\n", __func__);
    // stack实际上不算是容器，而是容器适配器，内部可以使用vector, list 或 deque实现
    stack<int> s1;
    stack<int, list<int>> s2;
    stack<int, vector<int>> s3;
    s1.push(1);
    cout << s1.top() << endl;
    s1.pop();

    s2.push(1);
    cout << s2.top() << endl;
    s2.pop();

    s3.push(1);
    cout << s3.top() << endl;
    s3.pop();
}

void test_queue() {
    printf("-------------------------- %s -------------------------\n", __func__);
    // list实际上不算是容器，而是容器适配器，内部可以使用list 或 deque实现
    queue<int> q1;
    queue<int, list<int> > q2;
    q1.push(1);
    q1.push(2);
    cout << q1.front() << q1.back() << endl;
    q1.pop();
    q1.pop();

    q2.push(1);
    q2.push(2);
    cout << q2.front() << q2.back() << endl;
    q2.pop();
    q2.pop();
}

template<class T>
ostream &operator<<(ostream &os, const vector<T> &lst) {
    for (auto &t: lst)
        os << t << " ";
    return os;
}

void test_heap() {
    printf("-------------------------- %s -------------------------\n", __func__);
    vector<int> heap;
    // push_heap会将对vector中最后一个元素进行上溯 percolate up
    for (int i = 0; i < 10; ++i) {
        heap.push_back(i);
        push_heap(heap.begin(), heap.end());
        cout << heap << endl;
    }
    // pop_heap会将第一个元素移动到最后，并执行下溯和上溯，保证堆的结构
    pop_heap(heap.begin(), heap.end());
    cout << heap << endl;
    // 先pop再push，原vector不会有任何变化
    push_heap(heap.begin(), heap.end());
    cout << heap << endl;
    // 通过不断地pop_heap可以实现排序，sort_heap就是基于这个原理
    sort_heap(heap.begin(), heap.end());
    cout << heap << endl;

    // 将一个无序的vector转换成堆的结构：
    // 其算法是从最后一个父节点开始，从右至左，从下至上得保证堆的结构
    make_heap(heap.begin(), heap.end());
    cout << heap << endl;
}

void test_priority_queue() {
    printf("-------------------------- %s -------------------------\n", __func__);
    priority_queue<int> pq;
    for (int x : {1, 5, 4, 2, 42, 7, 0}) {
        pq.push(x);
    }
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;
}

template<class T>
ostream &operator<<(ostream &os, const forward_list<T> &lst) {
    for (auto &t: lst)
        os << t << " ";
    return os;
}

void test_forward_list() {
    printf("-------------------------- %s -------------------------\n", __func__);
    forward_list<int> fl;
    for (int i = 0; i < 10; ++i)
        fl.push_front(i);
    cout << fl << endl;

    for (auto it = fl.begin(); it != fl.end(); ++it) {
        it = fl.insert_after(it, -1);
    }
    cout << fl << endl;

    for (auto it = fl.begin(); it != fl.end(); ) {
        if ((*it) != -1) {
            it = fl.erase_after(it);
        } else {
            ++it;
        }
    }
    cout << fl << endl;
}


int main() {
    test_iterator();
    test_vector();
    test_list();
    test_deque();
    test_stack();
    test_queue();
    test_heap();
    test_priority_queue();
    test_forward_list();
    return 0;
}